﻿using System;

namespace SpatialHashLib.Topology.Indexing
{
    public partial class Chain<T>
    {
        const int kInitialSize = 4;

        Link[] links;

        int head;
        int tail;
        int free;
        int count;
        int last;

        public Chain()
        {
            links = new Link[kInitialSize];
            head = tail = free = last = -1;
        }

        public int Count
        {
            get { return count; }
        }

        public int Length
        {
            get { return links.Length; }
        }

        public int Head
        {
            get { return head; }
        }

        public int Tail
        {
            get { return tail; }
        }

        public T this[int index]
        {
            get
            {
                return links[index].Item;
            }
        }

        public int Trim()
        {
            if (last < 0)
                return 0;

            int amount = links.Length - last + 1;

            if (amount > 0)
                links = links.Trim(amount);

            return amount;
        }

        public int AddFirst(T item)
        {
            int index;

            if (head < 0)
                index = head = tail = Add(item, -1, -1);
            else
                index = head = Add(item, -1, head);

            return index;
        }

        public int AddLast(T item)
        {
            int index;

            if (head < 0)
                index = head = tail = Add(item, -1, -1);
            else
                index = tail = Add(item, tail, -1);

            return index;
        }

        public int AddBefore(T item, int index)
        {
            if (index < 0 || index == head)
                return AddFirst(item);

            return Add(item, links[index].Previous, index);
        }

        public int AddAfter(T item, int index)
        {
            if (index < 0 || index == tail)
                return AddLast(item);

            return Add(item, index, links[index].Next);
        }

        public int Previous(int index)
        {
            int previous = index < 0 ? -1 : links[index].Previous;

            if (previous < 0)
                return -1;

            return previous;
        }

        public int Next(int index)
        {
            int next = index < 0 ? -1 : links[index].Next;

            if (next < 0)
                return -1;

            return next;
        }

        int Add(T item, int previous, int next)
        {
            int index;

            if (free < 0)
            {
                index = count;
                links = links.EnsureSize(index);
            }
            else
            {
                index = free;
                free = links[free].Next;
            }

            links[index] = new Link() { Item = item, Previous = previous, Next = next };

            ++count;

            if (previous >= 0)
                links[previous].Next = index;

            if (next >= 0)
                links[next].Previous = index;

            if (index > last)
                last = index;

            return index;
        }

        public bool Remove(int index)
        {
            if (index < 0)
                return false;

            count--;

            if (index == head)
                head = links[index].Next;
            else if (index == tail)
                tail = links[index].Previous;

            int previous = links[index].Previous;
            int next = links[index].Next;

            if (previous > -1)
                links[previous].Next = links[index].Next;

            if (next > -1)
                links[next].Previous = links[index].Previous;

            links[index] = new Link() { Previous = -1, Next = free };

            if (head < 0 || tail < 0)
                head = tail = free = -1;
            else
                free = index;

            return true;
        }

        public void Clear()
        {
            head = tail = free = last = -1;
            Array.Clear(links, 0, links.Length);
        }
    }
}
